﻿using System;

namespace SortOf
{
    public class BinarySearchTree<T> : BinaryTree<T> where T : IComparable
    {
        public void InOrder(BinaryTreeNode<T> theRoot)
        {
            if (!(theRoot == null))
            {
                InOrder(theRoot.left);
                theRoot.DisplayNode();
                InOrder(theRoot.right);
            }
        }
        //Er moet een parameter key ingegeven worden, vervolgens wordt er naar de key gezocht, om deze vervolgens te verwijderen, de inhoud wordt dan op null gezet
        public bool Delete(T key)
        {
            BinaryTreeNode<T> current = root;
            BinaryTreeNode<T> parant = root;
            bool isLeftChild = true;

            while (current.data.CompareTo(key) != 0)
            {
                parant = current;
                if (key.CompareTo(current.data) < 0)
                {
                    isLeftChild = true;
                    current = current.left;
                }
                else
                {
                    isLeftChild = false;
                    current = current.right;
                }

                if (current == null)
                {
                    return false;
                }
            }

            if (current.left == null && current.right == null)
            {
                if (current == root)
                {
                    root = null;
                }
                else if (isLeftChild)
                {
                    parant.left = null;
                }
                else
                {
                    parant.right = null;
                }
            }
            else if (parant.right == null)
            {
                if (current == root)
                {
                    root = current.left;
                }
                else if (isLeftChild)
                {
                    parant.left = current.left;
                }
                else
                {
                    parant.right = current.right;
                }
            }
            else if (current.left == null)
            {
                if (current == root)
                {
                    root = current.right;
                }
                else if (isLeftChild)
                {
                    parant.left = parant.right;
                }
                else
                {
                    parant.right = current.right;
                }
            }
            else
            {
                BinaryTreeNode<T> successor = getSuccessor(current);
                if (current == root)
                {
                    root = successor;
                }
                else if (isLeftChild)
                {
                    parant.left = successor;
                }
                else
                {
                    parant.right = successor;
                }
                successor.left = current.left;
            }

            return true;
        }

        //Er wordt gekeken of er nog iets onder het object hangt die verwijderd wordt, als dit het geval is, moet de data eronder eerst verplaatst worden
        public BinaryTreeNode<T> getSuccessor(BinaryTreeNode<T> delNode)
        {
            BinaryTreeNode<T> successorParant = delNode;
            BinaryTreeNode<T> successor = delNode;
            BinaryTreeNode<T> current = delNode.right;

            while (current != null)
            {
                successorParant = current;
                successor = current;
                current = current.left;
            }
            if (successor != delNode.right)
            {
                successorParant.left = successor.right;
                successor.right = delNode.right;
            }
            return successor;
        }
    }
}
